import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

        private int getHeight(TreeNode root){
            if(root == null){
                return 0;
            }
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            if(left == -1 || right == -1 || Math.abs(left - right) > 1){
                return -1;
            }
            return Math.max(left, right) + 1;
        }

        public boolean isBalanced(TreeNode root) {
            return getHeight(root) > -1;
        }



}
